﻿/*
 * Malte Frerichs
 * Melvin Bos
 * Jasper ter Weeme
 */

using System;
using System.Collections.Generic;

namespace SortOf
{
    public class HeapSort : ISort
    {
        private void Sort<T>(IList<T> list, int i, int m) where T : IComparable<T>
        {
           	T Temp = list[i];
            int j = i * 2 + 1;

            // deel heap maken; root en twee childs
            while (j <= m)
            {
                if (j < m)
                {
                    if (list[j].CompareTo(list[j + 1]) < 0)
                    {
                        j = j + 1;
                    }
                }

                if (Temp.CompareTo(list[j]) < 0)
                {
                    list[i] = list[j];
                    i = j;
                    j = 2 * i + 1;
                }
                else
                {
                    j = m + 1;
                }
            }

            list[i] = Temp;
        }

        public void Apply<T>(IList<T> list) where T : IComparable<T>
        {
            int i;

            // heap genereren
            for (i = (list.Count - 1) / 2; i >= 0; i--)
            {
                Sort(list, i, list.Count - 1);
            }

            // heap sorteren
            for (i = list.Count - 1; i >= 1; i--)
            {
                T temp = list[0];
                list[0] = list[i];
                list[i] = temp;
                Sort(list, 0, i - 1);
            }

        }
    }
}
